// 给定一个二叉树，检测它是否左右对称的
// 思路，递归
// 递归遍历当前节点的左右子节点
function isSymmetric(root) {
    function check(left, right) {
        if (!left && !right) {
            return true
        } else if ((left && !right) || (!left &&right)) {
            return false
        } else if (left.val !== right.val) {
            return false
        }
        return check(left.left, right.right) && check(left.right, right.left)
    }
    if (!root) {
        return true
    }
    return check(root.left, root.right)
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: {
            val: 3,
            left: {
                val: 4,
                left: null,
                right: null
            },
            right: null
        },
    },
    right: {
        val: 2,
        left: {
            val: 3,
            left: null,
            right: {
                val: 4,
                left: null,
                right: null
            }
        },
        right: null
    },
};

console.log(isSymmetric(root))

// 思路2，队列
function isSymmetric2(root) {
    let queue = []
    if (root) {
        queue.push(root.left, root.right)
    }
    while (queue.length) {
        let leftNode = queue.shift()
        let rightNode = queue.shift()
        if (!leftNode && !rightNode) {
            continue
        }
        if (!leftNode || !rightNode || leftNode.val !== rightNode.val) {
            return false
        }
        queue.push(leftNode.left)
        queue.push(rightNode.right)
        queue.push(leftNode.right)
        queue.push(rightNode.left)
    }
    return true
}
console.log(isSymmetric2(root))